package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2021/3/1
 * @description: 124. 二叉树中的最大路径和
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */
public class C_124_二叉树中的最大路径和 {

	static C_124_二叉树中的最大路径和 action = new C_124_二叉树中的最大路径和();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		// 3
		TreeNode root = TreeNode.stringToTreeNode("[1,2,3]");
		int res = action.maxPathSum(root);
		System.out.println("res = " + res);
	}

	/**
	 * 最大值
	 */
	int maxValue = Integer.MIN_VALUE;

	/**
	 * 由于只需要求出最大值即可，这是一种考虑子过程的结果而不是子过程的过程。
	 * 二叉树的特征决定了每一个根节点的特殊性：如果下边的节点想往上，必须经过根节点。
	 * 那么是否可以用  DP 来求解呢？
	 * DP：以每个根节点包含在路径内的单向值。
	 * dp[i] = tree[i] + max(dp[left],dp[right],0)
	 * （max 函数分别代表选择了左节点/右节点/只有根节点 进行 dp 的传递）
	 * --
	 * 关键在于需要记录子过程的最大值，同时将子过程最为子部分时的最大值进行继续递归！
	 * 关键在于处理好这两个递归。
	 * @param root
	 * @return
	 */
	public int maxPathSum(TreeNode root) {
		if (root.left == null && root.right == null) {
			return root.val;
		}
		postOrder(root);
		return maxValue;
	}

	private int postOrder(TreeNode root) {
		int max = 0, left = 0, right = 0;
		if (root.left != null) {
			int tLeft = postOrder(root.left);
			//如果 子树的和小于 0 -> 不采用
			if (tLeft > 0) {
				left = tLeft;
				max = Math.max(max, left);
			}
		}
		if (root.right != null) {
			int tRight = postOrder(root.right);
			if (tRight > 0) {
				right = tRight;
				max = Math.max(max, right);
			}
		}
		//由于路径必须至少要有一个节点
		//对于本次递归而言，情况只有三种：left+root;right+root;left+right+root
		//由于前面已经对 小于 0 的情况进行了过滤，又只需要求出最大值，那么只需要进行相加即可。
		maxValue = Math.max(maxValue, root.val + left + right);

		return root.val + max;
	}
}
